package com.zy.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * @description: 归并排序
 * @author: zhaoyi
 * @create: 2019-11-06 21:56
 * 归并的条件是两个子数据都是有序的
 * 先写合并两个有序集合merge
 * 再写递归过程mergeSort
 **/

public class MergeSort<T extends Comparable<? super T>> {


    public void sort(List<T> list) {
        if (list == null || list.size() <= 1) {
            return;
        }
        mergeSort(0, list.size() - 1, list);
    }

    void mergeSort(int left, int right, List<T> result) {
        if (left >= right) {
            return;
        }
        int q = (left + right) / 2;
        mergeSort(left, q, result);
        mergeSort(q + 1, right, result);
        merge(left, q, right, result);
    }

    void merge(int left, int mid, int right, List<T> result) {
        System.out.println("left: " + left + " mid: " + mid + " right: " + right);
        int size = (right - left) + 1;
        List<T> tmp = new ArrayList<>();
        int ls = left;
        int rs = mid + 1;
        for (int i = 0; i < size; i++) {
            if (rs > right) {
                tmp.add(result.get(ls));
                ls++;
            } else if (ls > mid) {
                tmp.add(result.get(rs));
                rs++;
            } else if (result.get(ls).compareTo(result.get(rs)) > 0) {
                tmp.add(result.get(rs));
                rs++;
            } else {
                tmp.add(result.get(ls));
                ls++;
            }
        }
        for (int i = 0; i < tmp.size(); i++) {
            result.set(left + i, tmp.get(i));
        }

    }


}
